package com.cyy.test_t_2_;
/**
 * 剑指Offer 面试题26 
 * 复杂链表的复制
 * 时间限制：1秒	空间限制：32768K
 * 题目描述
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
 * 另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
 * （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
 */

import com.cyy.test.util.RandomListNode;

/**
 * 解法一：
 * 先不管m_pSibling指针，将链表当做一个单链表复制，然后再遍历原链表，依次复制m_pSibling指针。
 * 但由于寻找新链表m_pSibling指针指向的结点需要遍历，因此时间复杂度为O(n^2)
 * 解法二：
 * 解法一的时间复杂度主要耗费在m_pSibling复制过程中需要遍历，而避免遍历的方法之一就是hash表，
 * 因此可以考虑建立一个原结点N和新结点N'的映射关系，这样在复制m_pSibling的时候，在新链表中寻
 * 找结点时直接查表即可。
 * 解法三：寻找时空效率更高的解法。
 * 第一步：复制链表，只是这个时候的复制，是把新的结点复制到原结点的后面，即N1->N1'->N2->N2'，
 * 这样m_pSibling指向的结点在新链表中也就是原结点的m_pNext结点
 * 第二步：将第一步得到的链表拆分即可。
 */

public class t_26 {
	
	public RandomListNode Clone(RandomListNode pHead)
    {
        
		if(pHead == null) {
			return null;
		}
		
		//复制连接点
		CloneNodes(pHead);
		
		//连接随机指针
		CloneSiblingNodes(pHead);
		
		//拆分链表
		return ReconnecteNodes(pHead);
    }

	private void CloneNodes(RandomListNode pHead) {
		if(pHead == null) {
			return;
		}
		
		RandomListNode pNode = pHead;
		while(pNode != null){
			RandomListNode pCloned = new RandomListNode(pNode.label);
			pCloned.next = pNode.next;
			pCloned.random = null;
			
			pNode.next = pCloned;
			pNode = pCloned.next;
		}
	}
	
	private void CloneSiblingNodes(RandomListNode pHead) {
		RandomListNode pNode = pHead;
		while(pNode != null){
			RandomListNode pCloned = pNode.next;
			if(pNode.random != null){
				pCloned.random = pNode.random.next;
			}
			
			pNode = pCloned.next;
		}
	}
	
	private RandomListNode ReconnecteNodes(RandomListNode pHead) {
		RandomListNode pNode = pHead;
		RandomListNode pClonedHead = null;
		RandomListNode pClonedNode = null;
		
		if(pNode != null){
			pClonedHead = pClonedNode = pNode.next;
			pNode.next = pClonedNode.next;
			pNode = pNode.next;
		}
		
		while(pNode != null){
			pClonedNode.next = pNode.next;
			pClonedNode = pClonedNode.next;
			pNode.next = pClonedNode.next;
			pNode = pNode.next;
		}
		return pClonedHead;
	}
}
